Stack Practice

Question:

Remember that wonderful Python list we talked about eariler? It turns out that stack functionality is already built into it!

The Python documentation shows how you can use built-in funtions to turn your Python list into a stack. pop() is a given function, and append() is equivalent to a push function.

Of course, this functionality makes stack manipulation in Python all too easy. Let's make our own Stack class to see how a stack really works under the hood.

Start Quiz:

algorithmsP3.py

"""Add a couple methods to our LinkedList class,
and use that to implement a Stack.
You have 4 functions below to fill in:
insert_first, delete_first, push, and pop.
Think about this while you're implementing:
why is it easier to add an "insert_first"
function than just use "append"?"""

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None
        
class LinkedList(object):
    def __init__(self, head=None):
        self.head = head
        
    def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

    def insert_first(self, new_element):
        "Insert new element as the head of the LinkedList"
        pass

    def delete_first(self):
        "Delete the first (head) element in the LinkedList as return it"
        pass

class Stack(object):
    def __init__(self,top=None):
        self.ll = LinkedList(top)

    def push(self, new_element):
        "Push (add) a new element onto the top of the stack"
        pass

    def pop(self):
        "Pop (remove) the first element off the top of the stack and return it"
        pass
    
# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)

# Start setting up a Stack
stack = Stack(e1)

# Test stack functionality
stack.push(e2)
stack.push(e3)
print stack.pop().value
print stack.pop().value
print stack.pop().value
print stack.pop()
stack.push(e4)
print stack.pop().value

Solution:

There's a solution below. We had two options here—either pop and push from the first element in our linked list, or pop and push from the last element. We already had a function, append() , that adds an element to the end.

Why didn't we just come up with a function for removing the last element and call it a day? Every operation on a linked list must start with the head. append() thus traverses the whole list, taking O(n). Any operation on the last element requires us to traverse everything, so even though we had to write a new method our code will run much faster if we push/pop from the first element in a linked list.

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

    def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

    def insert_first(self, new_element):
        new_element.next = self.head
        self.head = new_element

    def delete_first(self):
        if self.head:
            deleted_element = self.head
            temp = deleted_element.next
            self.head = temp
            return deleted_element
        else:
            return None

class Stack(object):
    def __init__(self,top=None):
        self.ll = LinkedList(top)

    def push(self, new_element):
        self.ll.insert_first(new_element)

    def pop(self):
        return self.ll.delete_first()

INSTRUCTOR NOTE:

Here's an alternative solution to delete_first() - https://gist.github.com/adarsh0806/02d8e1d54d510294e75dfbc0d9bd7059

Benefits of this method:

1) this version has fewer lines of code with no loss of functionality
2) this version clears out the next field of the deleted element (good practice, even though it's not in the specification)

Next Concept